package com.lw.leetcode.topology.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 *
 * topology
 * 207. 课程表
 * @author liw
 * @version 1.0
 * @date 2021/7/15 11:26
 */
public class CanFinish {

    public static void main(String[] args) {
        CanFinish test = new CanFinish();
//        int[][] arr = {{1, 0}, {0, 3}, {4, 0}};
//        int k = 4;
//        int[][] arr = {{1, 0}, {0, 3}, {5, 3}};
//        int k = 4;
//        int[][] arr = {{1,0}, {0, 3}, {3, 6}};
//        int k = 4;
//        int[][] arr = {{1,0}, {0, 1}};
//        int k = 2;
//        int[][] arr = {{1,0}};
//        int k = 2;
        int[][] arr = {};
        int k = 2;
        boolean b = test.canFinish(k, arr);
        System.out.println(b);

    }


    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0 || prerequisites[0].length == 0) {
            return true;
        }
        int length = prerequisites.length;
        Stack<Integer> stack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        Map<Integer, List<Integer>> all = new HashMap<>();
        for (int i = 0; i < length; i++) {
            int[] arr = prerequisites[i];
            List<Integer> item = all.computeIfAbsent(arr[0], k -> new ArrayList<>());
            item.add(arr[1]);
            map.putIfAbsent(arr[0], 0);
            map.merge(arr[1], 1, (a, b) -> a + b);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 0) {
                stack.add(entry.getKey());
            }
        }
        int count = 0;
        int size = map.size();
        while (!stack.isEmpty() && count < size) {
            Integer pop = stack.pop();
            List<Integer> list = all.get(pop);
            count++;
            if (list == null) {
                continue;
            }
            for (Integer item : list) {
                int v = map.get(item) - 1;
                if (v == 0) {
                    stack.add(item);
                }
                map.put(item, v);
            }
        }
        return stack.isEmpty() && count == size;
    }
}
